#include <vector>
#include <unordered_map>
#include <algorithm>

#include "constants.h"
#include "classes.h"
#include "tools.h"
#include "optimizer_tools.h"
#include "optimizer_local.h"
using namespace std;

OptLocal::OptLocal(AssignInfo &assign_info)
{
    this->assign_info = &assign_info;
    vector<BwType> _tmp(N, LOW);
    this->edge_site_bw_type_vec.reserve(T);
    this->center_site_bw_type_vec.reserve(T);
    for (int t = 0; t < T; ++t)
    {
        this->edge_site_bw_type_vec.push_back(_tmp);
        this->center_site_bw_type_vec.push_back(LOW);
    }
}

double OptLocal::opt(double edge_low_quantile, double edge_hight_quantile,
                     double center_low_quantile, double center_hight_quantile,
                     bool ignore_center_site_cost, bool always_keep_center_cost_no_increase)
{
    this->edge_low_index = ceil(edge_low_quantile * T) - 1;
    this->edge_hight_index = ceil(edge_hight_quantile * T) - 1;
    this->center_low_index = ceil(center_low_quantile * T) - 1;
    this->center_hight_index = ceil(center_hight_quantile * T) - 1;

    this->ignore_center_site_cost = ignore_center_site_cost;
    this->always_keep_center_cost_no_increase = always_keep_center_cost_no_increase;

    this->edge_site_score = 0.0;
    this->center_site_score = 0.0;

    this->refresh_state();

    this->total_score = this->edge_site_score + this->center_site_score;
    cout << "------";
    cout << "total_score:" << (long long)this->total_score
         << " edge_site_score:" << (long long)this->edge_site_score
         << " center_site_score:" << (long long)this->center_site_score
         << endl;

    for (int t = 0; t < T; ++t)
    {
        this->find_local_optimize_assign_t(t);
    }
    return this->edge_site_score;
}

void OptLocal::refresh_state()
{

    for (int site_id = 0; site_id < N; ++site_id)
    {
        this->refresh_edge_site_state(site_id);
    }
    this->refresh_center_site_state();
}

void OptLocal::refresh_edge_site_state(int site_id)
{
    vector<TAssign *> &assign_vec = this->assign_info->assign_vec;
    int bw_allo_list[T];
    for (int t = 0; t < T; ++t)
    {
        bw_allo_list[t] = assign_vec[t]->site_total_bw[site_id];
    }
    vector<int> bw_sorted_index = arg_sort(bw_allo_list, T, true);

    int target_bw = bw_allo_list[bw_sorted_index[config_info.quantile_index]];
    this->edge_site_score += get_edge_site_score(target_bw, site_info.site_bw_upper[site_id]);

    this->edge_site_low_bw[site_id] = max(bw_allo_list[bw_sorted_index[this->edge_low_index]], config_info.base_cost);
    this->edge_site_high_bw[site_id] = max(bw_allo_list[bw_sorted_index[this->edge_hight_index]], config_info.base_cost);

    for (int i = 0; i < this->edge_low_index; ++i)
    {
        this->edge_site_bw_type_vec[bw_sorted_index[i]][site_id] = LOW;
    }

    for (int i = this->edge_low_index; i <= this->edge_hight_index; ++i)
    {
        this->edge_site_bw_type_vec[bw_sorted_index[i]][site_id] = CRUCIAL;
    }

    for (int i = this->edge_hight_index + 1; i < T; ++i)
    {
        this->edge_site_bw_type_vec[bw_sorted_index[i]][site_id] = BUFFER;
    }

    int _T = T - 1;
    for (int t = 0; t < _T; ++t)
    {
        if ((this->edge_site_bw_type_vec[t][site_id] == BUFFER) && (this->edge_site_bw_type_vec[t + 1][site_id] == BUFFER))
        {
            this->edge_site_bw_type_vec[t][site_id] = RADICAL;
        }
    }
    if (this->edge_site_bw_type_vec[_T][site_id] == BUFFER)
    {
        this->edge_site_bw_type_vec[_T][site_id] = RADICAL;
    }
}

void OptLocal::refresh_center_site_state()
{
    vector<TAssign *> &assign_vec = this->assign_info->assign_vec;
    long long bw_allo_list[T];
    for (int t = 0; t < T; ++t)
    {
        bw_allo_list[t] = assign_vec[t]->center_site_bw;
    }
    vector<int> bw_sorted_index = arg_sort(bw_allo_list, T, true);

    long long target_bw = bw_allo_list[bw_sorted_index[config_info.quantile_index]];
    this->center_site_score = get_center_site_score(target_bw);

    this->center_site_low_bw = bw_allo_list[bw_sorted_index[this->center_low_index]];
    this->center_site_high_bw = bw_allo_list[bw_sorted_index[this->center_hight_index]];

    for (int i = 0; i < this->center_low_index; ++i)
    {
        this->center_site_bw_type_vec[bw_sorted_index[i]] = LOW;
    }

    for (int i = this->center_low_index; i <= this->center_hight_index; ++i)
    {
        this->center_site_bw_type_vec[bw_sorted_index[i]] = CRUCIAL;
    }

    for (int i = this->center_hight_index + 1; i < T; ++i)
    {
        this->center_site_bw_type_vec[bw_sorted_index[i]] = RADICAL;
    }
}

void OptLocal::find_local_optimize_assign_t(int t)
{
    TAssign *tAssign = this->assign_info->assign_vec[t];
    tAssign->refresh_inherited_bw();
    tAssign->refresh_total_bw();
    process_overflow_t(tAssign);

    vector<int> safe_bw_uppers = this->get_safe_bw_uppers(t, tAssign);
    for (int site_id = 0; site_id < N; ++site_id)
    {
        //如果当前节点小于base_cost，那么不做分发
        if (tAssign->site_total_bw[site_id] <= config_info.base_cost)
        {
            continue;
        }

        //当前节点的带宽值小于0.95，大于等于0.94，并且高于base_cost
        if (this->edge_site_bw_type_vec[t][site_id] == CRUCIAL)
        {
            // cout << "这是一个CRUCIAL，带宽为：" << initial_solution.assign_vec[t]->site_total_bw[site_id] << endl;
            this->drop_bandwidth_from_site(site_id, tAssign, safe_bw_uppers);
        }
    }
}

void OptLocal::drop_bandwidth_from_site(int site_id, TAssign *tAssign, vector<int> &safe_bw_uppers)
{
    SiteAlloSortIter bw_allo_sort_iter(tAssign->site_stream_to_allo_info[site_id], false);
    AlloNode *iter;

    int to_site_id = -1;
    bw_allo_sort_iter.next(iter);
    while ((iter) && (tAssign->site_total_bw[site_id] >= this->edge_site_low_bw[site_id]))
    {
        //核心代码。判断这个流能否扔出去，以及查找一个可以转移的目标站点，inplace更新to_site_id
        if (this->check_throw_and_select_to_site_id(to_site_id, site_id, iter, tAssign, safe_bw_uppers))
        {
            tAssign->transfer(iter->stream_id, iter->client_id, to_site_id);
        }
        bw_allo_sort_iter.next(iter);
    }
}

bool OptLocal::check_throw_and_select_to_site_id(int &to_site_id, int from_site_id, AlloNode *iter, TAssign *tAssign, vector<int> &safe_bw_uppers)
{
    const int &client_id = iter->client_id;
    const int &stream_id = iter->stream_id;
    const int &bandwidth = iter->bandwidth;

    const int &client_connect_site_num = client_info.client_connect_num[client_id];
    const vector<int> &client_to_sites = client_info.client_to_sites[client_id];

    for (int index = 0; index < client_connect_site_num; ++index)
    {
        int current_to_site_index = (++this->circle_time_state) % client_connect_site_num;
        int current_to_site_id = client_to_sites[current_to_site_index];

        if (current_to_site_id == from_site_id)
        {
            continue;
        }

        if ((tAssign->site_total_bw[current_to_site_id] + bandwidth) > safe_bw_uppers[current_to_site_id])
        {
            continue;
        }

        if (!this->is_center_cost_decrease(from_site_id, current_to_site_id, bandwidth, tAssign, stream_id))
        {
            continue;
        }

        to_site_id = current_to_site_id;
        return true;
    }
    return false;
}

bool OptLocal::is_center_cost_decrease(int from_site_id, int to_site_id, int bandwidth, TAssign *tAssign, int stream_id)
{
    if (this->ignore_center_site_cost)
    {
        return true;
    }

    int to_site_increase_cost = max(bandwidth - tAssign->site_stream_to_allo_info[to_site_id][stream_id].largest_bw, 0);

    int from_site_decrease_cost = 0;
    if (tAssign->site_stream_to_allo_info[from_site_id][stream_id].count == 1)
    {
        from_site_decrease_cost = bandwidth;
    }
    else
    {
        //说明要转移的节点可能是最大的，也可能是次大的，只要不是最大，转移成本就不会降低。
        if (tAssign->site_stream_to_allo_info[from_site_id][stream_id].largest_bw == bandwidth)
        {
            //说明当前要转移的是最大的，那就计算转移降低的量是多少
            from_site_decrease_cost = bandwidth - tAssign->site_stream_to_allo_info[from_site_id][stream_id].head->next_site_allo->bandwidth;
        }
        else
        {
            from_site_decrease_cost = 0;
        }
    }

    if (this->always_keep_center_cost_no_increase)
    {
        return from_site_decrease_cost >= to_site_increase_cost;
    }
    else
    {
        long long new_center_bw = tAssign->center_site_bw - from_site_decrease_cost + to_site_increase_cost;

        switch (this->center_site_bw_type_vec[tAssign->t])
        {
        case LOW:
            return new_center_bw <= this->center_site_low_bw;
            break;
        case CRUCIAL:
            return from_site_decrease_cost >= to_site_increase_cost;
            break;
        case RADICAL:
            return true;
            break;
        case BUFFER:
            cout << "ERROR: center site shouldn't be BUFFER" << endl;
            throw exception();
            break;
        }
    }
    return false;
}

vector<int> OptLocal::get_safe_bw_uppers(int t, TAssign *tassign)
{
    vector<int> bw_upper(N, 0);
    vector<BwType> &edge_site_bw_types = this->edge_site_bw_type_vec[t];
    for (int site_id = 0; site_id < N; site_id++)
    {
        const int &low_bw = this->edge_site_low_bw[site_id];
        int &_upper = bw_upper[site_id];
        const BwType &bw_type = edge_site_bw_types[site_id];
        switch (bw_type)
        {
        case LOW:
            _upper = low_bw;
            break;
        case CRUCIAL:
            _upper = max(tassign->site_total_bw[site_id], config_info.base_cost);
            break;
        case BUFFER: // BUFFER一定不会出现在最后一个时刻
        {
            _upper = (low_bw - tassign->next_tassign->site_allocated_bw[site_id]) / INHERIT_RATE;
            _upper = max(_upper, tassign->site_total_bw[site_id]);
            break;
        }
        case RADICAL:
        {
            if (tassign->next_tassign)
            {
                _upper = (site_info.site_bw_upper[site_id] - tassign->next_tassign->site_allocated_bw[site_id]) / INHERIT_RATE;
                _upper = max(_upper, tassign->site_total_bw[site_id]);
            }
            else
            {
                _upper = site_info.site_bw_upper[site_id];
            }
            break;
        }
        }
        _upper = min(_upper, site_info.site_bw_upper[site_id]);
    }
    return bw_upper;
}